package com.lizk.leetcode.List_node_section_reverse;

public class ListNodeSectionReverse {

    /**
     * lzk 后面这里配上图解
     * 第一次循环定位到开始处理的前一个指针pre
     * 确定开始处理的指针start
     * 确定第一次处理的尾指针tail,也就是下一次要反转到pre下一个节点的数据.
     * 每次循环处理,将start.next = tail.next;tail.next = pre.next;pre.next=tail;这三步相当于把start指针移动到了当前循环过的节点的最末尾,把tail节点移动到pre的下一个节点.
     * tail=start.next;重新设置tail的值,作为下一次循环处理的节点
     * @param head
     * @param m
     * @param n
     * @return
     */
    public static ListNode sort2(ListNode head, int m, int n){
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre = dummy;
        for (int i = 0; i < m - 1; i++) {
            pre = pre.next;
        }
        ListNode start = pre.next;
        ListNode tail = start.next;
        for (int i = m; i < n; i++) {
            start.next = tail.next;
            tail.next = pre.next;
            pre.next = tail;
            tail = start.next;
        }
        return dummy.next;
    }

    /**
     *
     * @param head
     * @param m
     * @param n
     * @return
     */
    public static ListNode sort(ListNode head, int m, int n) {
        ListNode one = null;
        ListNode two = null;
        ListNode three = null;
        ListNode four = null;

        int index = 1;
        ListNode tmp = new ListNode(-1);
        tmp.next = head;
        while (index <= n && tmp.next != null) {
            ListNode next = tmp.next;
            if (index == m){
                one = tmp;
                two = tmp.next;
            }
            if (m < index && index <= n){
                if (three == null){
                    three = tmp;
                }else {
                    tmp.next = three;
                    three = tmp;
                }
            }
            if (index == n){
                four = next.next;
                next.next = three;
                three = next;
            }
            tmp = next;
            index++;
        }
        one.next = three;
        two.next = four;
        if (m == 1){
            return one.next;
        }else{
            return head;
        }
    }



    public static void main(String[] args) {
        ListNode a = new ListNode(1);
        a.next = new ListNode(2);
        a.next.next = new ListNode(3);
        a.next.next.next = new ListNode(4);
        a.next.next.next.next = new ListNode(5);
        a.next.next.next.next.next = new ListNode(6);
       /* long begin = System.nanoTime();

        for (int i = 0; i < 1000000; i++) {
            sort2(a, 2, 5);
        }

        long mid = System.nanoTime();
        for (int i = 0; i < 1000000; i++) {
            sort(a, 1, 6);
        }
        long end = System.nanoTime();


        System.out.println(mid - begin);
        System.out.println(end - mid);
*/

        sort(a, 1, 6).print();
    }



    public static class ListNode {
        public ListNode next;
        public int value;

        public ListNode(int value) {
            this.value = value;
            next = null;
        }

        /**
         * 打印链表
         */
        public void print() {
            ListNode tmp = new ListNode(-1);
            tmp.next = this;
            while (tmp.next != null) {
                tmp = tmp.next;
                System.out.println(tmp.value);
            }
        }
    }
}
